#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdbool.h>
#include <string.h>

typedef struct {
	int width;
	int height;	//wymiary magazynu width x height (<= 100.000.000)
	int ** occupying_robot_id;	//pola oznaczajace ktory/czy jakis robot juz przechodzi przez dane pole
} magazine;

typedef struct {
	char direction;
	int length;
} order;

typedef struct {
	int id;		//numer robota
	bool used;
	struct {		//pozycja startowa ustalona przez algorytm
		int x;
		int y;
	} start_field;
	int program_length;	//dlugosc programu robota
	order * orders;		//program robota
} robot;

void print_input(magazine warehouse, robot * robots, int size_to_cover, int robot_count) {
	int i, j;
	printf("%d %d\n%d\n%d\n", warehouse.width, warehouse.height, size_to_cover, robot_count);
	for (i = 0; i < robot_count; i++) {
		printf("%d\n%d\n", robots[i].id, robots[i].program_length);
		for (j = 0; j < robots[i].program_length; j++) {
			printf("%c %d\n", robots[i].orders[j].direction, robots[i].orders[j].length);
		}
	}

}

void print_magazine(magazine warehouse) {
	int i, j;
	for (i = 0; i < warehouse.height; i++) {
		for (j = 0; j < warehouse.width; j++) {
			printf("%d ", warehouse.occupying_robot_id[j][i]);
		}
		printf("\n");
	}
}

void print_output(int used_robots_count, robot * robots, int robot_count) {
	int i, used;
	printf("%d\n", used_robots_count);
	for (i = 0, used = 0; i < robot_count && used < used_robots_count; i++) {
		if (robots[i].used == true) {
			printf("%d %d %d\n", robots[i].id, robots[i].start_field.x + 1, robots[i].start_field.y + 1);
			used++;
		}
	}
}

int parse_input(magazine * warehouse, robot ** robots, int * size_to_cover, int * robot_count) {
	int i, j;
	fscanf(stdin, "%d %d", &((*warehouse).width), &((*warehouse).height));
	if ((* warehouse).width *(*warehouse).height > 100000000) {
		fprintf(stderr, "Too big magazine! Size of the magazine must be less or equal to 100.000.000\n");
		exit(-2);
	}
	fscanf(stdin, "%d", size_to_cover);
	if (*size_to_cover > (*warehouse).width * (*warehouse).height) {
		fprintf(stderr, "Size to cover is bigger than size of the magazine!\n");
		exit(-3);
	}
	fscanf(stdin, "%d", robot_count);
	if (*robot_count > 3 * (*warehouse).width * (*warehouse).height) {
		fprintf(stderr, "There's too many robots!\n");
		exit(-4);
	}
	warehouse->occupying_robot_id = (int **)malloc(sizeof(int *) * warehouse->width);
	for (i = 0; i < warehouse->width; i++) {
		warehouse->occupying_robot_id[i] = (int *)malloc(sizeof(int) * warehouse->height);
		for (j = 0; j < warehouse->height; j++) {
			warehouse->occupying_robot_id[i][j] = 0;
		}
	}
	*robots = (robot *)malloc(sizeof(robot)*(*robot_count));
	for (i = 0; i < *robot_count; i++) {
		fscanf(stdin, "%d", &((*robots)[i].id));
		fscanf(stdin, "%d\n", &((*robots)[i].program_length));
		(*robots)[i].orders = (order *)malloc(sizeof(order) * (*robots)[i].program_length);
		for (j = 0; j < (*robots)[i].program_length; j++) {
			fscanf(stdin, "%[WENS]", &((*robots)[i].orders[j].direction));
			fscanf(stdin, "%d\n", &((*robots)[i].orders[j].length));
		}
	}
	return 0;
}

void free_memory(robot ** robots, magazine * warehouse, int robot_count) {
	int i;
	for (i = 0; i < (*warehouse).width; i++) {
		free((*warehouse).occupying_robot_id[i]);
	}
	free((*warehouse).occupying_robot_id);
	for (i = 0; i < robot_count; i++) {
		free((*robots)[i].orders);
	}
	free(*robots);
}

int place(magazine warehouse, int x, int y, robot * current_robot) {
	int i, j, covered = 0;
	int tmpx = x, tmpy = y;
	//printf("x=%d y=%d width=%d height=%d\n", x, y, warehouse.width, warehouse.height);
	order * current_robot_orders = (* current_robot).orders;
	if (warehouse.occupying_robot_id[x][y] != 0) {
		covered = -1;
	}
	for (i = 0; i < (* current_robot).program_length && covered != 1; i++) {
		order order_i = current_robot_orders[i];
		switch (order_i.direction) {
		case 'N':
			if (y - order_i.length < 0) {
				covered = -1;
				break;
			}
			for (j = 0; j <= order_i.length; j++) {
				if (warehouse.occupying_robot_id[x][y - j] != 0) {
					covered = -1;
				}
			}
			y -= order_i.length;
			break;
		case 'S':
			if (y + order_i.length >= warehouse.height) {
				covered = -1;
				break;
			}			
			for (j = 0; j <= order_i.length; j++) {
				if (warehouse.occupying_robot_id[x][y + j] != 0) {
					covered = -1;
				}
			}
			y += order_i.length;
			break;
		case 'W':
			if (x - order_i.length < 0) {
				covered = -1;
				break;
			}
			for (j = 0; j <= order_i.length; j++) {
				if (warehouse.occupying_robot_id[x - j][y] != 0) {
					covered = -1;
				}
			}
			x -= order_i.length;
			break;
		case 'E':
			if (x + order_i.length >= warehouse.width) {
				covered = -1;
				break;
			}
			for (j = 0; j <= order_i.length; j++) {
				if (warehouse.occupying_robot_id[x + j][y] != 0) {
					covered = -1;
				}
			}
			x += order_i.length;
			break;
		default:
			break;
		}
	}
	x = tmpx;
	y = tmpy;
	if (covered != -1) {
		//print_magazine(warehouse);
		warehouse.occupying_robot_id[x][y] = (* current_robot).id;
		(* current_robot).start_field.x = x;
		(* current_robot).start_field.y = y;
		covered = 1;
		for (i = 0; i < (* current_robot).program_length; i++) {
			order order_i = current_robot_orders[i];
			for (j = 0; j < order_i.length; j++) {
				switch (order_i.direction) {
				case 'N':
					y--;
					break;
				case 'S':
					y++;
					break;
				case 'W':
					x--;
					break;
				case 'E':
					x++;
					break;
				default:
					break;
				}
				if (warehouse.occupying_robot_id[x][y] != (* current_robot).id) {
					warehouse.occupying_robot_id[x][y] = (* current_robot).id;
					covered++;
				}
					
			}
		}	
		//print_magazine(warehouse);
	}
	return covered;
}

int remove_robot(magazine warehouse, int x, int y, robot current_robot) {
	int i,j, covered = 1;
	warehouse.occupying_robot_id[x][y] = 0;
	for (i = 0; i < current_robot.program_length; i++) {
		order order_i = current_robot.orders[i];
		for (j = 0; j < order_i.length; j++) {
			switch (order_i.direction) {
			case 'N':
				y--;
				break;
			case 'S':
				y++;
				break;
			case 'W':
				x--;
				break;
			case 'E':
				x++;
				break;
			default:
				break;
			}
			if (warehouse.occupying_robot_id[x][y] == current_robot.id) {
				warehouse.occupying_robot_id[x][y] = 0;
				covered++;
			}
				
		}
	}
	//printf("Removed=%d %d\n", covered, current_robot.id);
	return covered;
}

int place_robots(magazine warehouse, robot * robots, int size_to_cover, int robot_count, int * chosen_count) {
	int i, j, k;
	if (size_to_cover <= 0) {
		//printf("Solution found!\n");
		//print_magazine(warehouse);
		return -1;
	}
	for (i = 0; i < warehouse.width; i++) {
		for (j = 0; j < warehouse.height; j++) {
			if (warehouse.occupying_robot_id[i][j] == 0) {
				for (k = 0; k < robot_count; k++) {
					if (robots[k].used == false) {
						int result = place(warehouse, i, j, &robots[k]);
						if (result > 0) {
							robots[k].used = true;
							(*chosen_count)++;
							//print_magazine(warehouse);
							//printf("%d\n", size_to_cover - result);
							//printf("%d covered\n", result);
							if (place_robots(warehouse, robots, size_to_cover - result, robot_count, chosen_count) == -1) {
								return -1;
							}
							size_to_cover -= result;
							robots[k].used = false;
							(*chosen_count)--;
							size_to_cover += remove_robot(warehouse, i, j, robots[k]);
						}
					}
				}
			}
		}
	}
	return 0;
	//print_magazine(warehouse);
}

int main(int argc, char ** argv) {

	int size_to_cover;	//minimalna liczba pol magazynu do pokrycia
	int robot_count;	//liczba robotow <= 3xy
	magazine warehouse;
	robot ** robots = (robot **)malloc(sizeof(robot *));

	int chosen_robots_count = 0;

	//Input parsing

	//fprintf(stderr, "Parsing input...\n");
	if (parse_input(&warehouse, robots, &size_to_cover, &robot_count) == -1) {
		perror("Input parsing");
		return -1;
	}
	//fprintf(stderr, "Done!\n");

	//Algorithm

	place_robots(warehouse, *robots, size_to_cover, robot_count, &chosen_robots_count);
	//printf("%d\n", size_to_cover);

	//Output printing

	//fprintf(stderr, "Printing output...\n");
	//print_magazine(warehouse);
	print_output(chosen_robots_count, *robots, robot_count);
	//fprintf(stderr, "Done!\n");

	//fprintf(stderr, "Freeing memory...\n");
	free_memory(robots, &warehouse, robot_count);
	free(robots);
	//fprintf(stderr, "Done!\n");

	return 0;
}
